package Stack_Queue;

import java.util.ArrayDeque;
import java.util.Queue;

public class 用队列实现栈 {
}

//双队列
class MyStack1 {
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    public MyStack1() {
        queue1 = new ArrayDeque<>();
        queue2 = new ArrayDeque<>();
    }

    public void push(int x) {
        queue1.offer(x);
    }

    public int pop() {
        if (queue1.size() == 1) return queue1.poll();
        while (queue1.size() != 1) queue2.offer(queue1.poll());
        int r = queue1.poll();
        queue1 = queue2;
        queue2 = new ArrayDeque<>();
        return r;
    }

    public int top() {
        if (queue1.size() == 1) return queue1.peek();
        while (queue1.size() != 1) queue2.offer(queue1.poll());
        int r = queue1.peek();
        queue2.offer(queue1.poll());
        queue1 = queue2;
        queue2 = new ArrayDeque<>();
        return r;
    }

    public boolean empty() {
        return queue1.isEmpty();
    }
}

//单队列
class MyStack2 {
    Queue<Integer> queue;

    public MyStack2() {
        queue = new ArrayDeque<>();
    }

    public void push(int x) {
        queue.offer(x);
    }

    public int pop() {
        if (queue.size() == 1) return queue.poll();
        int size = queue.size();
        while (size-- != 1) queue.offer(queue.poll());
        return queue.poll();
    }

    public int top() {
        if (queue.size() == 1) return queue.peek();
        int size = queue.size();
        while (size-- != 1) queue.offer(queue.poll());
        int r = queue.peek();
        queue.offer(queue.poll());
        return r;
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}
